package 数据结构练习.summer;

public class day6 {
    /*
    给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
    如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     */
    public int searchInsert(int[] nums, int target) {
        int i = -1;
        //如果target比最小的元素小说明没有该元素应该添加到0索引
        if (nums[0] > target) return 0;
        for (i = 0; i < nums.length - 1; i++) {

            if (nums[i] == target) {
                return i;
            } else if (nums[i] < target && nums[i + 1] > target) {
                return i + 1;
            }
        }
        if (nums[nums.length - 1] == target) return nums.length - 1;
        return nums.length;
    }

    /*
    假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
    你可以通过调用bool isBadVersion(version)接口来判断版本号 version 是否在单元
    测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
    https://leetcode.cn/problems/first-bad-version
     */
    public int firstBadVersion(int n) {
        return bad(0, n);
    }

    private int bad(int begin, int end){
        if (begin>=end)return 0;
        int mid=(end-begin)/2+begin;
        //这里是为防止陷入无限递归，文字解释不了要画图
        if (end-begin==1){
            if (mid==begin){
                return end;
            }else if (mid==end){
                return begin;
            }
        }
        //没有isBadVersion()方法暂时注释
        /*if (isBadVersion(mid)){
            if (isBadVersion(mid-1)){
                end=mid;
            }else {
                return mid;
            }
        }else{
            begin=mid;
        }*/
        return bad(begin,end);
    }

    /*
    //官方解答
    public int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left < right) { // 循环直至区间左右端点相同
            int mid = left + (right - left) / 2; // 防止计算时溢出
            if (isBadVersion(mid)) {
                right = mid; // 答案在区间 [left, mid] 中
            } else {
                left = mid + 1; // 答案在区间 [mid+1, right] 中
            }
        }
        // 此时有 left == right，区间缩为一个点，即为答案
        return left;
    }
     */
}
